#define _CRT_SECURE_NO_WARNINGS 1

class WordDictionary
{
    struct DictTree
    {
        std::vector<DictTree*> _next;
        bool _end;

        DictTree()
            : _next(std::vector<DictTree*>(26, nullptr))
            , _end(false)
        { }
    };

public:
    WordDictionary()
        : _root(new DictTree)
    { }

    void addWord(string word)
    {
        DictTree* cur = _root;
        for (const char ch : word)
        {
            if (cur->_next[ch - 'a'] == nullptr)
            {
                cur->_next[ch - 'a'] = new DictTree;
            }
            cur = cur->_next[ch - 'a'];
        }

        cur->_end = true;
    }

    bool search(string word)
    {
        return _search(word, _root, 0, word.size());
    }

private:
    bool _search(const std::string& word, DictTree* cur, size_t index, size_t n)
    {
        if (index == n)
        {
            return cur->_end;
        }

        if (word[index] == '.')
        {
            for (char ch = 'a'; ch <= 'z'; ++ch)
            {
                if (cur->_next[ch - 'a'] != nullptr)
                {
                    bool ret = _search(word, cur->_next[ch - 'a'], index + 1, n);
                    if (ret == true) return true;
                }
            }
            return false;
        }
        else
        {
            if (cur->_next[word[index] - 'a'] == nullptr) return false;
            else return _search(word, cur->_next[word[index] - 'a'], index + 1, n);
        }
    }

    DictTree* _root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */